1. Field of the Invention
The invention in general relates to random number generators, and more particularly to a random number generator that generates true binary random sequences.
2. Description of the Related Art
It has become widely recognized that random number generators are fundamentally important in the computer age. See Stephen K. Park and Keith W. Miller, “Random Number Generators: Good Ones Are Hard To Find”, in Computing Practices, October 1988, V. 31, No. 10, pp. 1192-1201. Random number generators may be divided into two types: true random number generators, which generate numbers from a non-deterministic source, and pseudorandom number generators, which generate numbers from a deterministic algorithm. A high quality random number generator is necessary for functions from Monte Carlo-based studies used in computer modeling of the global economy, to cryptography, to parapsychological studies, to marketing research, to lottery games. Thus, it is not surprising that the literature reveals hundreds of random number generators. See, for example, the following U.S. Pat. No. 3,423,683 issued to E. S. Kelsey et al.; U.S. Pat. No. 3,445,591 issued to D. R. Koehler et al.; U.S. Pat. No. 3,612,845 issued to Reed C. Lawlor; U.S. Pat. No. 3,706,941 issued to Charles E. Cohn; U.S. Pat. No. 3,725,677 issued to Reed C. Lawlor; U.S. Pat. No. 3,758,873 issued to Herbert E. Miller; U.S. Pat. No. 4,183,088 issued to Robert E. Simmons; U.S. Pat. No. 4,395,703 issued to Gerald V. Piosenka; U.S. Pat. No. 4,513,386 issued to Sydney Glazer; U.S. Pat. No. 4,578,598 issued to Mark E. Faulaber; U.S. Pat. No. 4,858,122 issued to William Kreisner; and U.S. Pat. No. 5,239,494 issued to Edmund C. Golbeck; and the following papers: Masatugu Isida and Hiroji Ikeda, “Random Number Generator” in Proceedings of the Institute of Statistical Mechanics, 1956, pp. 119-126; Helmut Schmidt, “A Quantum Mechanical Random Number Generator for PSI Tests” in The Journal of Parapsychology, circa 1972, pp. 219-224; and Teruyuki Izimi, “Universal Random Signal Generator”, in Electrical Engineering in Japan, Vol. 99, No. 4, 1979, pp. 124-130. Yet, there are few “random number generators” on the market today that actually produce random numbers. High quality true random number generators are still in the realm of large-budget projects at major research institutions.
A random number generator (RNG) that interfaces directly with a computer would be of particular value since random numbers are often used in conjunction with a computer, and a direct interface allows a researcher or other computer user to simply call up the number generator and use the numbers it produces within the context of their program. See for example, James H. Macomber and Charles S. White, “An n-Dimensional Uniform Random Number Generator Suitable for IBM-Compatible Microcomputers”, in Interfaces, Vol. 20, No. 3, May-June 1990, pp. 49-59. Because the most common computers today are digital, RNG's that interface with computers generally generate a binary random sequence (BRS) rather than a sequence of analog or floating point numbers, which BRS's may be used as generated, converted to uniform distributed numbers, converted to Gaussian distributed numbers or converted to any other type of distribution. Many computer programs that utilize random numbers are statistical in nature; that is, they depend on large numbers of events which are averaged in some manner to reach a valid conclusion. For this to be accomplished over reasonable time periods, these programs require that large quantities of binary bits or random numbers be generated in short periods. True random number generators usually trade off speed for randomness, thus are relatively slow. As a result, at this time it appears that the available random number generators that interface directly with computers are all software-based, pseudorandom number generators. See, Macomber and White, supra; Niederreiter, supra; and Park and Miller, supra.
While pseudorandom number generators are suitably fast for a computer, they cannot generate a true random number because they are generated by algorithms which are deterministic, i.e. they are totally predictable given knowledge of the algorithm used. In addition, most pseudorandom number generators used with computers produce number sequences which fail even moderately stringent statistical randomness tests. It is known that to generate a true random number, one must start with a non-deterministic signal, such as white noise generated by a resistor, diode, or other electronic device, the time between radioactive particle decay, the locations of detected photo-events, or other signal source that is essentially random because it is based on quantum mechanics or other statistically random process. See, for example, U.S. Pat. No. 4,176,399 issued to Jean-Claude Hoffmann et al., and the following papers: G. B. Agnew, “Random Sources For Cryptographic Systems”, in Lecture Notes in Computer Science—Advances in Cryptology—Eurocrypt '87, Springer-Verlag, Berlin, 1987, pp. 77-81; and Anthony J. Martino and G. Michael Morris, “Optical Random Number Generator Based On Photoevent Locations”, in Applied Optics, Vol. 30, No. 8, Mar. 10, 1991, pp. 981-989. We have referred to these signals as “essentially” random, because even these non-deterministic sources exhibit some defects because they are generated with macroscopic, real world devices.
It is known that the randomness in such non-deterministic signals can be improved by digital processing. See for example, U.S. Pat. No. 4,545,024 issued to David P. Maher et al., and the paper: Helmut Schmidt, “Quantum-Mechanical Random-Number Generator”, in Journal of Applied Physics, Vol. 41, No. 2, February 1970, pp. 462-468. In particular it is known to improve randomness by using EXCLUSIVE OR (XOR) gates to discard certain bits. See, U.S. Pat. No. 4,355,366 issued to Sigmund N. Porter. It is also known to use comparators or other electronic devices to convert analog noise signals to binary signals. See, U.S. Pat. No. 4,545,024 cited above and H. Sutcliffe, “Noise-spectrum Measurement at Subaudio Frequencies”, in Proceedings of the IEEE, Vol. 112, No. 2, February 1965, pp. 301-309.
Despite the fact that all of the above has been known for many years, a practical, inexpensive, fast, high-quality true random number generator that interfaces directly with a computer is not presently available. In fact, some authorities maintain that such a device is not practically possible. See, Harald Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, Chapter 7, section 7.2, p. 164, Society For Industrial and Applied Mathematics, Philadelphia 1992; and Aaldert Compagner, “Definitions of Randomness”, American Journal of Physics, Vol. 59, No. 8, August 1991, pp. 700-705, at page 702. As a result, “random number generators” used with computers today are pseudo-random number generators.